# 10阶楼梯，每次上1台阶或者上2台阶，问一共有多少走法
# method 1: 递归效率低，可改用 method 2 循环
def fn(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    return fn(n - 1) + fn(n - 2)


print(fn(5))  # 8

# method 2: 循环
a = [0, 1, 2]
for i in range(3, 11):
    a.append(a[i - 1] + a[i - 2])
print(a[5])  # 8